Mi manual de algoritmos/version_actual/src/geometria/monotonechain.cpp

   1 // Convex Hull: Andrew's Monotone Chain Convex Hull
   2 // Complexity: O(n log n) (But lower constant than Graham Scan)
   3
   4 typedef long long CoordType;
   5
   6 struct Point {
   7   CoordType x, y;
   8   bool operator <(const Point &p) const {
   9     return x < p.x || (x == p.x && y < p.y);
  10   }
  11 };
  12
  13 // 2D cross product.  Returns a positive value, if OAB makes a
  14 // counter-clockwise turn, negative for clockwise turn, and zero
  15 // if the points are collinear.
  16 CoordType cross(const Point &O, const Point &A, const Point &B){
  17   return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
  18 }
  19
  20 // Returns a list of points on the convex hull in
  21 // counter-clockwise order.  Note: the last point in the returned
  22 // list is the same as the first one.
  23 vector<Point> convexHull(vector<Point> P){
  24   int n = P.size(), k = 0;
  25   vector<Point> H(2*n);
  26   // Sort points lexicographically
  27   sort(P.begin(), P.end());
  28   // Build lower hull
  29   for (int i = 0; i < n; i++) {
  30     while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
  31     H[k++] = P[i];
  32   }
  33   // Build upper hull
  34   for (int i = n-2, t = k+1; i >= 0; i--) {
  35     while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
  36     H[k++] = P[i];
  37   }
  38   H.resize(k);
  39   return H;
  40 }